1. Field
The information disclosed relates to online advertising. More particularly, the information disclosed relates to generating an optimization graph in an online advertising system.
2. Background Information
Online advertising is a form of promotion that uses the Internet and World Wide Web to deliver marketing messages on webpages to attract customers. Each webpage may include one or more locations on the page that are ready to receive an impression of an advertisement. An advertising system may refer to these as a supply of advertising inventory, which usually is made up of page impressions. In addition, the advertising system may have contractual obligations to serve a number of advertisements to the advertising inventory over a given amount of time. For example, the advertising system may be contracted to deliver two billion advertisements to webpages over thirty days. An advertising system may refer to these as advertising demand contracts.
In online advertising, a page impression should be suitable for a given advertisement. For example, a children's news webpage may be a good place to serve an advertisement for a toy, but not a good place to serve an advertisement that promotes a tobacco product. To keep track of this, the advertising system may maintain a graph that links the supply and the demand in a way that represents that allowable supply that can be used to satisfy a particular demand. However, advertising systems that process billions of impressions per day have a difficult time in handling arbitrarily large graphs representing such supply and demand.